package com.vincent.exam.search;

public class BinarySearch {
    /**
     * 二分法查找，针对有序的无重复数组
     * @param arr
     * @param val
     * @return
     */
    public int find(int[] arr, int val) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > val) {
                r = mid - 1;
            } else if (arr[mid] < val) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    /**
     * 请实现有重复数字的有序数组的二分查找。
     * 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一
     * 输出位置从1开始计算
     *
     * @param arr
     * @param val
     * @return
     */
    public int findWithRep(int[] arr, int val) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (mid > 0 && arr[mid - 1] >= val) {
                //因为有重复的数字，所以就算等于目标值也需要不断向左查找
                r = mid - 1;
            } else if (arr[mid] < val) {
                // 目标值比中间值都大，向右查找
                l = mid + 1;
            } else {
                return mid + 1;
            }
        }
        return arr.length + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[1000];
        for (int i = 0; i < 1000; i++) {
            arr[i] = i;
        }
        System.out.println(new BinarySearch().find(arr, 999));
    }
}
